#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
using namespace std;

namespace exercise
{
	class UnionFindSet
	{
	public:
		UnionFindSet(int n)
			:_ufs(n, -1)
		{}

		int Find(int x)
		{
			int root = x;
			while(_ufs[root] >= 0)
			{
				root = _ufs[root];
			}

			while (_ufs[x] >= 0)
			{
				int parent = _ufs[x];
				_ufs[x] = root;
				x = parent;
			}

			return root;
		}

		bool Uinon(int x, int y)
		{
			int root1 = Find(x);
			int root2 = Find(y);
			if (root1 == root2)
				return false;

			if (abs(_ufs[root1]) < abs(_ufs[root2]))
				swap(root1, root2);

			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
			return true;
		}

		size_t Size()
		{
			size_t count = 0;
			for (int i = 0; i < _ufs.size(); ++i)
				if (_ufs[i] < 0)
					count++;
			return count;
		}

		bool InSet(int x,int y)
		{
			return Find(x) == Find(y);
		}

	private:
		vector<int> _ufs;
	};
}